#include<bits/stdc++.h>

using namespace std;


const int N = 3e4 + 10 , M = 2 * N;
class Solution {
public:
    int h[N] , e[M] , ne[M] , idx;
    int n;
    int sum[N];//sum[u]表示u点向下走所以点的总和
    int cnt[N];//cnt[u]表示u点为root的子树的点的个数
    int up[N];//up[u]表示u点向上走所以点的总和
    void add(int a , int b)
    {
        e[idx] = b , ne[idx] = h[a] , h[a] = idx++;
    }
    void dfs_d(int u , int father)
    {
        for(int i = h[u] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if(j == father) continue;
            up[j] = up[u] + sum[u] - (sum[j] + cnt[j]) + n - cnt[j];
            // cout<<j<<" "<<up[j]<<endl;
            dfs_d(j , u);
        }
    }
    void dfs_u(int u , int father)
    {
        sum[u] = 0;
        cnt[u] = 1;
        for(int i = h[u] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if(j == father) continue;
            dfs_u(j , u);
            sum[u] += sum[j] + cnt[j];
            cnt[u] += cnt[j];
        }
    }
    vector<int> sumOfDistancesInTree(int _n, vector<vector<int>>& edges) {
        memset(h , -1 , sizeof h);
        memset(up , 0 , sizeof up);
        n = _n;
        idx = 0;
        for(auto e : edges)
        {
            int a = e[0] , b = e[1];
            add(a , b) , add(b , a);
        }
        dfs_u(0 , -1);
        // for(int i = 0 ; i < n ; ++i) 
        //     cout<<i<<" "<<sum[i]<<" "<<cnt[i]<<endl;
        dfs_d(0 , -1);
        // for(int i = 0 ; i < n ; ++i)
        //     cout<<i<<" "<<up[i]<<endl;
        vector<int> res;
        for(int i = 0 ; i < n ; ++i) res.push_back(sum[i] + up[i]);
        return res;
    }
};

int main()
{
    Solution s;
    int n = 6;
    vector<vector<int>> edges = {{0,1},{0,2},{2,3},{2,4},{2,5}};
    vector<int> res = s.sumOfDistancesInTree(n , edges);
    for(auto x : res) cout<<x<<" ";
    puts("");
    system("pause");
    return 0;
}